package Day2025_03_08;

import java.util.LinkedList;
import java.util.Queue;

public class LeeetCode200 {
    int[] dx = {0, 0, 1, -1};
    int[] dy = {1, -1, 0, 0};
    int ret = 0;
    public int numIslands(char[][] grid) {
        int n = grid.length, m = grid[0].length;
        Queue<int[]> q = new LinkedList<>();
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (grid[i][j] == '1') {
                    q.add(new int[]{i, j});
                    grid[i][j] = '0';
                    while (!q.isEmpty()) {
                        int[] tmp = q.poll();
                        int a = tmp[0], b = tmp[1];
                        for (int k = 0; k < 4; k++) {
                            int cur1 = a + dx[k], cur2 = b + dy[k];
                            if (cur1 >= 0 && cur1 < n && cur2 >= 0 && cur2 < m && grid[cur1][cur2] == '1') {
                                q.add(new int[]{cur1, cur2});
                                grid[cur1][cur2] = '0';
                            }
                        }
                    }
                    ret++;
                }
            }
        }
        return ret;
    }

    public static void main(String[] args) {
        LeeetCode200 leetCode200 = new LeeetCode200();
        System.out.println(leetCode200.numIslands(new char[][]{{'1', '1', '1', '1', '0'}, {'1', '1', '0', '1', '0'}, {'1', '1', '0', '0', '0'}, {'0', '0', '0', '0', '0'}}));
    }
}
